package org.learn.leetcode;
//实现int sqrt(int x)函数。
//
//        计算并返回x的平方根，其中x 是非负整数。
//
//        由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

public class MySqrt {
    //x的平方根

    public int mySqrt(int x) {
        // 特殊值判断
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }

        int left = 1;
        int right = x / 2;
        // 在区间 [left..right] 查找目标元素
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 了避免乘法溢出，用除法
            if (mid > x / mid) {
                // 下一轮搜索区间是 [left..mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索区间是 [mid..right]
                left = mid;
            }
        }
        return left;
    }

}
